Quantum algorithms are global random searching algorithms based on quantum mechanics, laws, and quantum effects. They are used for controlling a process or for processing data in a database, and more specifically, to control a process and/or including search-of-minima intelligent operations.
In a quantum search algorithm, each design variable is represented by a finite linear superposition of classical initial states with a sequence of elementary unitary steps manipulating the initial quantum state |i> (for the input) such that a measurement of the final state of the system yields the correct output. Usually, three principle operators, i.e., linear superposition (coherent states), entanglement and interference are used in the quantum search algorithm.
For a better comprehension on the field of application of the present invention, a brief description of quantum search algorithms is provided below.
Overview on Quantum Algorithms
The problems solved by quantum algorithms may be stated as follows:
                                        ⁢          Input                                                ⁢                                    A              ⁢                                                          ⁢              function              ⁢                                                          ⁢              f              ⁢                              :                            ⁢                                                          ⁢                                                {                                      0                    ,                    1                                    }                                n                                      →                                          {                                  0                  ,                  1                                }                            m                                                                              ⁢          Problem                                                ⁢                      Find            ⁢                                                  ⁢            a            ⁢                                                  ⁢            certain            ⁢                                                  ⁢            property            ⁢                                                  ⁢            of            ⁢                                                  ⁢                          f              .                                             
The structure of a quantum algorithm is outlined by a high level representation in the schematic diagram of FIG. 1. The input of a quantum algorithm is a function f from binary strings into binary strings. This function is represented as a map table, defining for every string its image. The function f is first encoded into a unitary matrix operator UF depending on f properties. This operator calculates f when its input and output strings are encoded into canonical basis vectors of a Complex Hilbert Space: UF maps the vector code of every string into the vector code of its image by f.
                                                                                                                                                                            ⁢                                          BOX                      ⁢                                                                                          ⁢                      1                      ⁢                                              :                                            ⁢                                                                                          ⁢                      UNITARY                      ⁢                                                                                          ⁢                      MATRIX                      ⁢                                                                                          ⁢                                              U                        F                                                                                                                                                                                                                                                                                                        A                      ⁢                                                                                          ⁢                      squared                      ⁢                                                                                          ⁢                      matrix                      ⁢                                                                                          ⁢                                              U                        F                                            ⁢                                                                                          ⁢                      on                      ⁢                                                                                          ⁢                      the                      ⁢                                                                                          ⁢                      complex                      ⁢                                                                                          ⁢                      field                      ⁢                                                                                          ⁢                      is                      ⁢                                                                                          ⁢                      unitary                      ⁢                                                                                          ⁢                      if                      ⁢                                                                                          ⁢                      its                                        ⁢                                                                                                                                                                                        inverse              ⁢                                                          ⁢              matrix              ⁢                                                          ⁢              coincides              ⁢                                                          ⁢              with              ⁢                                                          ⁢              its              ⁢                                                          ⁢              conjugate              ⁢                                                          ⁢              transpose              ⁢                              :                                                                                                      ⁢                              U            F                          -              1                                =                      U            F            t                                                  A        ⁢                                  ⁢        unitary        ⁢                                  ⁢        matrix        ⁢                                  ⁢        is        ⁢                                  ⁢        always        ⁢                                  ⁢        reversible        ⁢                                  ⁢        and        ⁢                                  ⁢        preserves        ⁢                                  ⁢        the        ⁢                                  ⁢        norm                                                          ⁢                  of          ⁢                                          ⁢                      vectors            .                              
When the matrix operator UF has been generated, it is embedded into a quantum gate G, which is a unitary matrix whose structure depends on the form of matrix UF and on the problem we want to solve. The quantum gate is the heart of a quantum algorithm. In every quantum algorithm, the quantum gate acts on an initial canonical basis vector (the same vector can always be chosen) to generate a complex linear combination (i.e., a superposition) of basis vectors as the output. This superposition contains all the information to answer the initial problem.
After the superposition has been created, a measurement takes place to extract this information. In quantum mechanics, the measurement is a non-deterministic operation that produces as output only one of the basis vectors in the entering superposition. The probability of every basis vector being the measurement output depends on its complex coefficient (probability amplitude) in the entering complex linear combination.
The segmental action of the quantum gate and of the measurement forms the quantum block. The quantum block is repeated k times to produce a collection of k basis vectors. Since the measurement is a non-deterministic operation, these basic vectors will not be necessarily identical and each one of them will encode a piece of the information needed to solve the problem.
The last part of the algorithm includes the interpretation of the collected basis vectors in order to get the right answer for the initial problem with a certain probability.
Encoder
The behavior of the encoder block is described in the detailed schematic diagram of FIG. 2. The function f is encoded into matrix UF in three steps.
Step 1
The map table of the function f: {0,1}n→{0,1}m is transformed into the map table of the injective function F: {0,1}n+m→{0,1}n+m such that:F(x0, . . . , xn−1, y0, . . . , ym−1)=(x0, . . . , xn−1, f(x0, . . . , xn−1)⊕(y0, . . . , ym−1))  (2)
The need to deal with an injective function comes from the requirement that UF is unitary. A unitary operator is reversible, so it can not map 2 different inputs in the same output. Since UF will be the matrix representation of F, F is supposed to be injective. If we directly used the matrix representation of the function f, we could obtain a non-unitary matrix since f could be non-injective. Injectivity is thus fulfilled by increasing the number of bits and considering the function F instead of the function f. The function f can always be calculated from F by putting (y0, . . . , ym−1)=(0, . . . , 0) in the input string and reading the last m values of the output string.
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                ⁢                                                                                                                        BOX                                          ⁢                                                                                                                                                                          ⁢                                          2                                          ⁢                                                                                      :                                                                                    ⁢                                                                                                                                                                          ⁢                                          XOR                                          ⁢                                                                                                                                                                          ⁢                                          OPERATOR                                                                                ⁢                                                                                                                                                                  ⊕                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  The                                        ⁢                                                                                                                                                                  ⁢                                        XOR                                        ⁢                                                                                                                                                                  ⁢                                        operator                                        ⁢                                                                                                                                                                  ⁢                                        between                                        ⁢                                                                                                                                                                  ⁢                                        two                                        ⁢                                                                                                                                                                  ⁢                                        binary                                        ⁢                                                                                                                                                                  ⁢                                        strings                                        ⁢                                                                                                                                                                  ⁢                                        p                                        ⁢                                                                                                                                                                  ⁢                                        and                                        ⁢                                                                                                                                                                  ⁢                                        q                                        ⁢                                                                                                                                                                  ⁢                                        of                                                                            ⁢                                                                                                                                                                                                                                                                                                                                                                                                                                  length                                ⁢                                                                                                                                  ⁢                                m                                ⁢                                                                                                                                  ⁢                                is                                ⁢                                                                                                                                  ⁢                                a                                ⁢                                                                                                                                  ⁢                                string                                ⁢                                                                                                                                  ⁢                                s                                ⁢                                                                                                                                  ⁢                                of                                ⁢                                                                                                                                  ⁢                                length                                ⁢                                                                                                                                  ⁢                                m                                ⁢                                                                                                                                  ⁢                                such                                ⁢                                                                                                                                  ⁢                                that                                ⁢                                                                                                                                  ⁢                                the                                ⁢                                                                                                                                  ⁢                                i                                ⁢                                                                  -                                                                ⁢                                th                                ⁢                                                                                                                                  ⁢                                digit                                ⁢                                                                                                                                  ⁢                                of                                                                                                                                                                                                                                                  s                          ⁢                                                                                                          ⁢                          is                          ⁢                                                                                                          ⁢                          calculated                          ⁢                                                                                                          ⁢                          as                          ⁢                                                                                                          ⁢                          the                          ⁢                                                                                                          ⁢                          exclusive                          ⁢                                                                                                          ⁢                          OR                          ⁢                                                                                                          ⁢                          between                          ⁢                                                                                                          ⁢                          the                          ⁢                                                                                                          ⁢                          i                          ⁢                                                      -                                                    ⁢                          th                          ⁢                                                                                                          ⁢                          digits                          ⁢                                                                                                          ⁢                          of                                                                                                                                                                                                            p                      ⁢                                                                                          ⁢                      and                      ⁢                                                                                          ⁢                      q                      ⁢                                              :                                                              ⁢                                                                                                                                                                                        p              =                              (                                                      p                    0                                    ,                  …                  ⁢                                                                          ,                                      p                                          n                      -                      1                                                                      )                                                                            q        =                  (                                    q              0                        ,            …            ⁢                                                  ,                          q                              n                -                1                                              )                                                  s          =                                    p              ⊕              q                        =                          (                                                                    (                                                                  p                        0                                            +                                              q                        0                                                              )                                    ⁢                                                                          ⁢                  mod                  ⁢                                                                          ⁢                  2                                ,                …                ⁢                                                                  ,                                                      (                                                                  p                                                  n                          -                          1                                                                    +                                              q                                                  n                          -                          1                                                                                      )                                    ⁢                                                                          ⁢                  mod                  ⁢                                                                          ⁢                  2                                            )                                      )            Step 2
The function F map table is transformed into a UF map table based upon the following constraint:∀sε{0,1}n+m: UF[τ(s)]=τ[F(s)]  (3)The code map τ: {0,1}n+m→c2n+m(c2n+m is the target Complex Hilbert Space) is such that:
            τ      ⁢              (        0        )              =                  (                                            1                                                          0                                      )            =                                                                0                        〉                    ⁢                                          ⁢                      τ            ⁡                          (              1              )                                      =                              (                                                            0                                                                              1                                                      )                    =                                                  1                        〉                                          τ      ⁡              (                              x            0                    ,          …          ⁢                                          ,                      x                          n              +              m              -              1                                      )              =                                        τ            ⁡                          (                              x                0                            )                                ⊗          …          ⊗                      τ            ⁡                          (                              x                                  n                  +                  m                  -                  1                                            )                                      =                                                      x              0                        ⁢                                                  ⁢            …            ⁢                                                  ⁢                          x                              n                +                m                -                1                                                        〉      Code τ maps bit values into complex vectors of dimension 2 belonging to the canonical basis of C2. Besides, using tensor product, τ maps the general state of a binary string of dimension n into a vector of dimension 2n. This reduces this state to the joint state of the n bits composing the register. Every bit state is transformed into the corresponding 2-dimesional basis vector, and then the string state is mapped into the corresponding 2n-dimesional basis vector by composing all bit-vectors through tensor products. In this sense a tensor product is the vector counterpart of state conjunction.
                                                                                                                                    BOX                      ⁢                                                                                          ⁢                      3                      ⁢                                              :                                            ⁢                                                                                          ⁢                      VECTOR                      ⁢                                                                                          ⁢                      TENSOR                      ⁢                                                                                          ⁢                                              PRODUCT                        ⁢                                                                                                  ⊗                                                                                                                                                                                                                                                                                                      The                ⁢                                                                  ⁢                tensor                ⁢                                                                  ⁢                product                ⁢                                                                  ⁢                between                ⁢                                                                  ⁢                two                ⁢                                                                  ⁢                vectors                ⁢                                                                  ⁢                of                ⁢                                                                  ⁢                dimensions                ⁢                                                                  ⁢                h                ⁢                                                                  ⁢                and                ⁢                                                                  ⁢                k                                                                                                            is              ⁢                                                          ⁢              a              ⁢                                                          ⁢              tensor              ⁢                                                          ⁢              product              ⁢                                                          ⁢              of              ⁢                                                          ⁢              dimension              ⁢                                                          ⁢                              h                ·                k                                      ,                          such              ⁢                                                          ⁢              that              ⁢                              :                                              ⁢                                                                                x        〉            ⊗                      y        〉              =                            (                                                                      x                  1                                                                                    …                                                                                      x                  h                                                              )                ⊗                  (                                                                      y                  1                                                                                    …                                                                                      y                  k                                                              )                    =                        (                                                                                          x                    1                                    ⁢                                      y                    1                                                                                                      …                                                                                                          x                    1                                    ⁢                                      y                    k                                                                                                      …                                                                                                          x                    h                                    ⁢                                      y                    1                                                                                                      …                                                                                                          x                    h                                    ⁢                                      y                    k                                                                                )                ⇒                                                                                                              ⁢                                                                            Physical                      ⁢                                                                                          ⁢                      interpretation                                        _                                    ⁢                                      :                                                  ⁢                                                                                                                                          If                ⁢                                                                  ⁢                a                ⁢                                                                  ⁢                component                ⁢                                                                  ⁢                of                ⁢                                                                  ⁢                a                ⁢                                                                  ⁢                complex                ⁢                                                                  ⁢                vector                ⁢                                                                  ⁢                is                                                                                        interpreted                ⁢                                                                  ⁢                as                ⁢                                                                  ⁢                the                ⁢                                                                  ⁢                probability                ⁢                                                                  ⁢                amplitude                                                                                        of                ⁢                                                                  ⁢                a                ⁢                                                                  ⁢                system                ⁢                                                                  ⁢                being                ⁢                                                                  ⁢                in                ⁢                                                                  ⁢                a                ⁢                                                                  ⁢                given                ⁢                                                                  ⁢                state                                                                                                          (                                      indexed                    ⁢                                                                                  ⁢                    by                    ⁢                                                                                  ⁢                    the                    ⁢                                                                                  ⁢                    component                    ⁢                                                                                  ⁢                    number                                    )                                ,                the                                                                                        tensor                ⁢                                                                  ⁢                product                ⁢                                                                  ⁢                between                ⁢                                                                  ⁢                two                ⁢                                                                  ⁢                vectors                                                                                        describes                ⁢                                                                  ⁢                the                ⁢                                                                  ⁢                joint                ⁢                                                                  ⁢                probability                                                                                        amplitude                ⁢                                                                  ⁢                of                ⁢                                                                  ⁢                two                ⁢                                                                  ⁢                systems                ⁢                                                                  ⁢                being                ⁢                                                                  ⁢                in                ⁢                                                                  ⁢                a                                                                                        joint                ⁢                                                                  ⁢                                  state                  .                                                                        